home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 290_02 / tblcmp.c < prev    next >
Text File  |  1990-05-12  |  47KB  |  1,607 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16.  
  17. #include "main.h"
  18. #include "misc.h"
  19. #include "tblcmp.h"
  20. #include "dfa.h"
  21. #include "nfa.h"
  22. #include "ecs.h"
  23.  
  24. extern int flexscan( void) ;        /* from scan.c */
  25.  
  26. /* bldtbl - build table entries for dfa state
  27.  *
  28.  * synopsis
  29.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  30.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  31.  *
  32.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  33.  * gives the number of the state to enter for a given equivalence class.
  34.  * totaltrans is the total number of transitions out of the state.  Comstate
  35.  * is that state which is the destination of the most transitions out of State.
  36.  * Comfreq is how many transitions there are out of State to Comstate.
  37.  *
  38.  * A note on terminology:
  39.  *    "protos" are transition tables which have a high probability of
  40.  * either being redundant (a state processed later will have an identical
  41.  * transition table) or nearly redundant (a state processed later will have
  42.  * many of the same out-transitions).  A "most recently used" queue of
  43.  * protos is kept around with the hope that most states will find a proto
  44.  * which is similar enough to be usable, and therefore compacting the
  45.  * output tables.
  46.  *    "templates" are a special type of proto.  If a transition table is
  47.  * homogeneous or nearly homogeneous (all transitions go to the same
  48.  * destination) then the odds are good that future states will also go
  49.  * to the same destination state on basically the same character set.
  50.  * These homogeneous states are so common when dealing with large rule
  51.  * sets that they merit special attention.  If the transition table were
  52.  * simply made into a proto, then (typically) each subsequent, similar
  53.  * state will differ from the proto for two out-transitions.  One of these
  54.  * out-transitions will be that character on which the proto does not go
  55.  * to the common destination, and one will be that character on which the
  56.  * state does not go to the common destination.  Templates, on the other
  57.  * hand, go to the common state on EVERY transition character, and therefore
  58.  * cost only one difference.
  59.  */
  60.  
  61. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  62. int state[], statenum, totaltrans, comstate, comfreq;
  63.  
  64. {
  65.     int extptr, extrct[2][CSIZE + 1];
  66.     int mindiff, minprot, i, d;
  67.     int checkcom;
  68.  
  69.     /* If extptr is 0 then the first array of extrct holds the result of the
  70.      * "best difference" to date, which is those transitions which occur in
  71.      * "state" but not in the proto which, to date, has the fewest differences
  72.      * between itself and "state".  If extptr is 1 then the second array of
  73.      * extrct hold the best difference.  The two arrays are toggled
  74.      * between so that the best difference to date can be kept around and
  75.      * also a difference just created by checking against a candidate "best"
  76.      * proto.
  77.      */
  78.  
  79.     extptr = 0;
  80.  
  81.     /* if the state has too few out-transitions, don't bother trying to
  82.      * compact its tables
  83.      */
  84.  
  85.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  86.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  87.  
  88.     else
  89.     {
  90.         /* checkcom is true if we should only check "state" against
  91.          * protos which have the same "comstate" value
  92.          */
  93.  
  94.         checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  95.  
  96.         minprot = firstprot;
  97.         mindiff = totaltrans;
  98.  
  99.         if ( checkcom )
  100.         {
  101.             /* find first proto which has the same "comstate" */
  102.             for ( i = firstprot; i != NIL; i = protnext[i] )
  103.                 if ( protcomst[i] == comstate )
  104.                 {
  105.                     minprot = i;
  106.                     mindiff = tbldiff( state, minprot, extrct[extptr] );
  107.                     break;
  108.                 }
  109.         }
  110.  
  111.         else
  112.         {
  113.             /* since we've decided that the most common destination out
  114.              * of "state" does not occur with a high enough frequency,
  115.              * we set the "comstate" to zero, assuring that if this state
  116.              * is entered into the proto list, it will not be considered
  117.              * a template.
  118.              */
  119.             comstate = 0;
  120.  
  121.             if ( firstprot != NIL )
  122.             {
  123.                 minprot = firstprot;
  124.                 mindiff = tbldiff( state, minprot, extrct[extptr] );
  125.             }
  126.         }
  127.  
  128.         /* we now have the first interesting proto in "minprot".  If
  129.          * it matches within the tolerances set for the first proto,
  130.          * we don't want to bother scanning the rest of the proto list
  131.          * to see if we have any other reasonable matches.
  132.          */
  133.  
  134.         if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  135.         { /* not a good enough match.  Scan the rest of the protos */
  136.             for ( i = minprot; i != NIL; i = protnext[i] )
  137.             {
  138.                 d = tbldiff( state, i, extrct[1 - extptr] );
  139.                 if ( d < mindiff )
  140.                 {
  141.                     extptr = 1 - extptr;
  142.                     mindiff = d;
  143.                     minprot = i;
  144.                 }
  145.             }
  146.         }
  147.  
  148.         /* check if the proto we've decided on as our best bet is close
  149.          * enough to the state we want to match to be usable
  150.          */
  151.  
  152.         if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  153.         {
  154.             /* no good.  If the state is homogeneous enough, we make a
  155.              * template out of it.  Otherwise, we make a proto.
  156.              */
  157.  
  158.             if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  159.                 mktemplate( state, statenum, comstate );
  160.  
  161.             else
  162.             {
  163.                 mkprot( state, statenum, comstate );
  164.                 mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  165.             }
  166.         }
  167.  
  168.         else
  169.         { /* use the proto */
  170.             mkentry( extrct[extptr], numecs, statenum,
  171.               prottbl[minprot], mindiff );
  172.  
  173.             /* if this state was sufficiently different from the proto
  174.              * we built it from, make it, too, a proto
  175.              */
  176.  
  177.             if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  178.                 mkprot( state, statenum, comstate );
  179.  
  180.             /* since mkprot added a new proto to the proto queue, it's possible
  181.              * that "minprot" is no longer on the proto queue (if it happened
  182.              * to have been the last entry, it would have been bumped off).
  183.              * If it's not there, then the new proto took its physical place
  184.              * (though logically the new proto is at the beginning of the
  185.              * queue), so in that case the following call will do nothing.
  186.              */
  187.  
  188.             mv2front( minprot );
  189.         }
  190.     }
  191. }
  192.  
  193.  
  194. /* cmptmps - compress template table entries
  195.  *
  196.  * synopsis
  197.  *    cmptmps();
  198.  *
  199.  *  template tables are compressed by using the 'template equivalence
  200.  *  classes', which are collections of transition character equivalence
  201.  *  classes which always appear together in templates - really meta-equivalence
  202.  *  classes.  until this point, the tables for templates have been stored
  203.  *  up at the top end of the nxt array; they will now be compressed and have
  204.  *  table entries made for them.
  205.  */
  206.  
  207. void cmptmps()
  208.  
  209. {
  210.     int tmpstorage[CSIZE + 1];
  211.     register int *tmp = tmpstorage, i, j;
  212.     int totaltrans, trans;
  213.  
  214.     peakpairs = numtemps * numecs + tblend;
  215.  
  216.     if ( usemecs )
  217.     {
  218.         /* c